
"""
450. 删除二叉搜索树中的节点
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        """
        利用二叉搜索树框架
        """
        if not root:
            return None

        if key == root.val:
            # 1.左右子树存在空
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            # 2.左右子树均不为空
            # 2.1找到右子树最小值
            min_right = self.min_right_tree(root.right)
            # 2.2删除右子树最小值
            root.right = self.deleteNode(root.right, min_right.val)
            # 2.3交换节点
            min_right.left = root.left
            min_right.right = root.right
            return min_right

        # 前序位置
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        # 中序位置
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        # 后序位置
        return root

    def min_right_tree(self, root) -> Optional[TreeNode]:
        """
        查询二叉搜索树最小值
        """
        while root.left:
            root = root.left
        return root

